<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Stephen A. Cook</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Stephen_A._Cook"> <link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Stephen_A_Cook rootpage-Stephen_A_Cook skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Stephen A. Cook</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p><b>Stephen Arthur Cook</b> <a href="Order_of_Ontario" title="Order of Ontario">OOnt</a> (* <a href="14._Dezember" title="14. Dezember">14. Dezember</a> <a href="1939" title="1939">1939</a> in <a href="Buffalo" title="Buffalo">Buffalo</a>, <a href="New_York_(Bundesstaat)" title="New York (Bundesstaat)">New York</a>) ist Professor der <a href="Informatik" title="Informatik">Informatik</a> an der <a href="University_of_Toronto" title="University of Toronto">University of Toronto</a> in <a href="Kanada" title="Kanada">Kanada</a>. Sein Hauptbetätigungsfeld ist die <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a>; Cook arbeitet neben seiner Lehrtätigkeit aber auch an der Schnittstelle von <a href="Logik" title="Logik">Logik</a> und <a href="Berechenbarkeitstheorie" title="Berechenbarkeitstheorie">Berechenbarkeitstheorie</a>.
</p><p>Cook wurde in der <a href="Theoretische_Informatik" title="Theoretische Informatik">theoretischen Informatik</a> berühmt durch den <a href="Satz_von_Cook" title="Satz von Cook">Satz von Cook</a>: „<a href="Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik" title="Erfüllbarkeitsproblem der Aussagenlogik">SAT</a> ist <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a>“. 1982 bekam er für diese Entdeckung den <a href="Turing_Award" title="Turing Award">Turing Award</a>.
</p><p>1990 hielt er einen Plenarvortrag auf dem <a href="Internationaler_Mathematikerkongress" title="Internationaler Mathematikerkongress">ICM</a> in Kyoto (<i>Computational complexity of higher type functions</i>).
</p>
<div class="mw-heading mw-heading2"><h2 id="Leben">Leben</h2></div>
<p>Cook wuchs als Sohn eines Chemie-Professors und einer Englischlehrerin in der Nähe von <a href="Buffalo" title="Buffalo">Buffalo</a>, <a href="New_York_(Bundesstaat)" title="New York (Bundesstaat)">New York</a>, auf. Ab 1957 studierte er Ingenieurwissenschaften an der <a href="University_of_Michigan" title="University of Michigan">University of Michigan</a>, wechselte nach zweieinhalb Jahren zur Mathematik und erreichte 1961 den Bachelor-Grad. Er studierte an der <a href="Harvard_University" title="Harvard University">Harvard University</a> weiter, wo ein Kurs seines späteren Doktorvaters <a href="Hao_Wang_(Mathematiker)" title="Hao Wang (Mathematiker)">Hao Wang</a> sein Interesse an Computern weckte. 1962 wurde er Master der Mathematik, 1966 mit der Thesis <i>On the Minimum Computation Time of Functions</i> (darin enthalten unter anderem der <a href="Toom-Cook-Algorithmus" title="Toom-Cook-Algorithmus">Toom-Cook-Algorithmus</a>) Ph.D. Nach Studiumsende wurde er Assistenzprofessor an der mathematischen Fakultät der <a href="University_of_California%2C_Berkeley" title="University of California, Berkeley">University of California, Berkeley</a>. Nachdem ihm dort eine <a href="Tenure-Track" title="Tenure-Track">Stelle auf Lebenszeit</a> verweigert wurde, wechselte er 1970 als außerordentlicher Professor an die neugegründete Fakultät für Informatik der University of Toronto, wo er zunächst auch Mathematik-Vorlesungen hielt.
</p><p>1971 formalisierte er in dem Paper <i>The Complexity of Theorem Proving Procedures</i> die <a href="Polynomialzeitreduktion" title="Polynomialzeitreduktion">Polynomialzeitreduktion</a> (auch: <i>Cook-Reduktion</i>), und begründete mit dem <a href="Satz_von_Cook" title="Satz von Cook">Satz von Cook</a> das Konzept der <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-Vollständigkeit</a> und im Besonderen das <a href="P-NP-Problem" title="P-NP-Problem">P-NP-Problem</a>. Im Jahr darauf wurde diese Arbeit von Cooks kurzzeitigem Berkeley-Kollegen <a href="Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a> popularisiert und durch <a href="Karps_21_NP-vollst%C3%A4ndige_Probleme" title="Karps 21 NP-vollständige Probleme">Karps 21 NP-vollständige Probleme</a> erweitert.
</p><p>1975 wurde er ordentlicher Professor, und 1985 erhielt er den Ehrentitel <i>University Professor</i>.
</p><p>Cook ist Steacie Fellow, Killiam Research Fellow, <a href="Association_for_Computing_Machinery" title="Association for Computing Machinery">ACM</a> Fellow, Fellow der <a href="Royal_Society_of_London" class="mw-redirect" title="Royal Society of London">Royal Society of London</a> und der <a href="Royal_Society_of_Canada" title="Royal Society of Canada">Royal Society of Canada</a>, und wurde in die <a href="National_Academy_of_Sciences" title="National Academy of Sciences">National Academy of Sciences</a> und die <a href="American_Academy_of_Arts_and_Sciences" title="American Academy of Arts and Sciences">American Academy of Arts and Sciences</a> gewählt. Er ist seit 1995 korrespondierendes Mitglied der <a href="Akademie_der_Wissenschaften_zu_G%C3%B6ttingen" class="mw-redirect" title="Akademie der Wissenschaften zu Göttingen">Akademie der Wissenschaften zu Göttingen</a>. 1982 erhielt er den Turing Award, 1999 erhielt er den CRM-Fields-Preis und war <a href="G%C3%B6del-Lecturer" class="mw-redirect" title="Gödel-Lecturer">Gödel-Lecturer</a>. Ihm wurden die <a href="Gerhard_Herzberg_Canada_Gold_Medal_for_Science_and_Engineering" title="Gerhard Herzberg Canada Gold Medal for Science and Engineering">Gerhard Herzberg Canada Gold Medal for Science and Engineering</a> für 2012 und der <a href="BBVA_Foundation_Frontiers_of_Knowledge_Award" class="mw-redirect" title="BBVA Foundation Frontiers of Knowledge Award">BBVA Foundation Frontiers of Knowledge Award</a> für 2015 zugesprochen.
</p><p>Cooks erster Doktorand war <a href="Walter_Savitch" title="Walter Savitch">Walter Savitch</a> (<a href="Satz_von_Savitch" title="Satz von Savitch">Satz von Savitch</a>), es folgten fast 30 weitere.
</p>
<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>
<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"><span class="mw-default-size" typeof="mw:File"><span title="Commons"></span></span></div><b><span class=""><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Stephen_Cook?uselang=de"><span lang="en">Commons</span>: Stephen Cook</a></span></b> – Sammlung von Bildern, Videos und Audiodateien</div>
<ul><li><a rel="nofollow" class="external text" href="http://www.cs.toronto.edu/~sacook/">Cooks Website an der Universität Toronto</a> (englisch)</li>
<li><a rel="nofollow" class="external text" href="https://conservancy.umn.edu/handle/11299/107226">Oral History Interview</a> des Charles Babbage Institute der University of Minnesota mit Stephen A. Cook 2002 (englisch)</li></ul>
<style data-mw-deduplicate="TemplateStyles:r260755238">
/* start https://de.wikipedia.org/ */
.mw-parser-output div.klappleiste{border:1px solid var(--dewiki-rahmenfarbe1);clear:both;font-size:95%;box-sizing:border-box;margin-top:1.5em;padding:2px}.mw-parser-output div.klappleiste:after{clear:both;content:"";display:block}.mw-parser-output div.klappleiste-bild{float:left;padding:2px}.mw-parser-output div.klappleiste-kopf{background:var(--dewiki-hintergrundfarbe5);color:var(--color-base,#202122);text-align:center;font-weight:bold}.mw-parser-output div.klappleiste.mw-collapsed .klappleiste-bild{display:none}.mw-parser-output div.klappleiste+div.klappleiste,.mw-parser-output div.klappleiste+link+div.klappleiste,.mw-parser-output div.klappleiste+link+link+div.klappleiste,.mw-parser-output div.klappleiste+link+style+div.klappleiste,.mw-parser-output div.klappleiste+style+div.klappleiste,.mw-parser-output div.klappleiste+style+style+div.klappleiste,.mw-parser-output div.klappleiste+style+link+div.klappleiste{margin-top:-1px}@media screen{html.skin-theme-clientpref-night .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}
/* end https://de.wikipedia.org/ */
</style>
<div class="klappleiste mw-collapsible navileiste navigation-not-searchable center" role="navigation">
<div class="klappleiste-kopf">Träger des <a href="Turing_Award" title="Turing Award">Turing Awards</a></div>
<div class="klappleiste-inhalt mw-collapsible-content">
<p>1966: <a href="Alan_J._Perlis" title="Alan J. Perlis">Perlis</a> |
1967: <a href="Maurice_V._Wilkes" title="Maurice V. Wilkes">Wilkes</a> |
1968: <a href="Richard_Hamming" title="Richard Hamming">Hamming</a> |
1969: <a href="Marvin_Minsky" title="Marvin Minsky">Minsky</a> |
1970: <a href="James_H._Wilkinson" title="James H. Wilkinson">Wilkinson</a> |
1971: <a href="John_McCarthy" title="John McCarthy">McCarthy</a> |
1972: <a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra</a> |
1973: <a href="Charles_Bachman" title="Charles Bachman">Bachman</a> |
1974: <a href="Donald_E._Knuth" title="Donald E. Knuth">Knuth</a> |
1975: <a href="Allen_Newell" title="Allen Newell">Newell</a>, <a href="Herbert_A._Simon" title="Herbert A. Simon">Simon</a> |
1976: <a href="Michael_O._Rabin" title="Michael O. Rabin">Rabin</a>, <a href="Dana_Scott" title="Dana Scott">Scott</a> |
1977: <a href="John_W._Backus" title="John W. Backus">Backus</a> |
1978: <a href="Robert_Floyd" title="Robert Floyd">Floyd</a> |
1979: <a href="Kenneth_E._Iverson" title="Kenneth E. Iverson">Iverson</a> |
1980: <a href="Tony_Hoare" title="Tony Hoare">Hoare</a> |
1981: <a href="Edgar_F._Codd" title="Edgar F. Codd">Codd</a> |
1982: <a class="mw-selflink selflink">Cook</a> |
1983: <a href="Ken_Thompson" title="Ken Thompson">Thompson</a>, <a href="Dennis_Ritchie" title="Dennis Ritchie">Ritchie</a> |
1984: <a href="Niklaus_Wirth" title="Niklaus Wirth">Wirth</a> |
1985: <a href="Richard_M._Karp" title="Richard M. Karp">Karp</a> |
1986: <a href="John_E._Hopcroft" title="John E. Hopcroft">Hopcroft</a>, <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan</a> |
1987: <a href="John_Cocke" title="John Cocke">Cocke</a> |
1988: <a href="Ivan_Sutherland" title="Ivan Sutherland">Sutherland</a> |
1989: <a href="William_Kahan" title="William Kahan">Kahan</a> |
1990: <a href="Fernando_Jos%C3%A9_Corbat%C3%B3" title="Fernando José Corbató">Corbató</a> |
1991: <a href="Robin_Milner" title="Robin Milner">Milner</a> |
1992: <a href="Butler_Lampson" title="Butler Lampson">Lampson</a> |
1993: <a href="Juris_Hartmanis" title="Juris Hartmanis">Hartmanis</a>, <a href="Richard_E._Stearns" title="Richard E. Stearns">Stearns</a> |
1994: <a href="Edward_Feigenbaum" title="Edward Feigenbaum">Feigenbaum</a>, <a href="Raj_Reddy" title="Raj Reddy">Reddy</a> |
1995: <a href="Manuel_Blum" title="Manuel Blum">Blum</a> |
1996: <a href="Amir_Pnueli" title="Amir Pnueli">Pnueli</a> |
1997: <a href="Douglas_C._Engelbart" title="Douglas C. Engelbart">Engelbart</a> |
1998: <a href="Jim_Gray" title="Jim Gray">Gray</a> |
1999: <a href="Frederick_P._Brooks" title="Frederick P. Brooks">Brooks</a> |
2000: <a href="Andrew_Yao" title="Andrew Yao">Yao</a> |
2001: <a href="Ole-Johan_Dahl" title="Ole-Johan Dahl">Dahl</a>, <a href="Kristen_Nygaard" title="Kristen Nygaard">Nygaard</a> |
2002: <a href="Ronald_L._Rivest" title="Ronald L. Rivest">Rivest</a>, <a href="Adi_Shamir" title="Adi Shamir">Shamir</a>, <a href="Leonard_Adleman" title="Leonard Adleman">Adleman</a> |
2003: <a href="Alan_Kay" title="Alan Kay">Kay</a> |
2004: <a href="Vinton_G._Cerf" title="Vinton G. Cerf">Cerf</a>, <a href="Robert_E._Kahn" title="Robert E. Kahn">Kahn</a> |
2005: <a href="Peter_Naur" title="Peter Naur">Naur</a> |
2006: <a href="Frances_E._Allen" title="Frances E. Allen">Allen</a> |
2007: <a href="Edmund_M._Clarke" title="Edmund M. Clarke">Clarke</a>, <a href="Allen_Emerson" title="Allen Emerson">Emerson</a>, <a href="Joseph_Sifakis" title="Joseph Sifakis">Sifakis</a> |
2008: <a href="Barbara_Liskov" title="Barbara Liskov">Liskov</a> |
2009: <a href="Charles_P._Thacker" title="Charles P. Thacker">Thacker</a> |
2010: <a href="Leslie_Valiant" title="Leslie Valiant">Valiant</a> |
2011: <a href="Judea_Pearl" title="Judea Pearl">Pearl</a> |
2012: <a href="Silvio_Micali" title="Silvio Micali">Micali</a>, <a href="Shafrira_Goldwasser" title="Shafrira Goldwasser">Goldwasser</a> |
2013: <a href="Leslie_Lamport" title="Leslie Lamport">Lamport</a> |
2014: <a href="Michael_Stonebraker" title="Michael Stonebraker">Stonebraker</a> |
2015: <a href="Whitfield_Diffie" title="Whitfield Diffie">Diffie</a>, <a href="Martin_Hellman" title="Martin Hellman">Hellman</a> |
2016: <a href="Tim_Berners-Lee" title="Tim Berners-Lee">Berners-Lee</a> |
2017: <a href="John_L._Hennessy" title="John L. Hennessy">Hennessy</a>, <a href="David_A._Patterson" title="David A. Patterson">Patterson</a> |
2018: <a href="Geoffrey_Hinton" title="Geoffrey Hinton">Hinton</a>, <a href="Yann_LeCun" title="Yann LeCun">LeCun</a>, <a href="Yoshua_Bengio" title="Yoshua Bengio">Bengio</a> |
2019: <a href="Edwin_Catmull" title="Edwin Catmull">Catmull</a>, <a href="Pat_Hanrahan" title="Pat Hanrahan">Hanrahan</a> |
2020: <a href="Alfred_V._Aho" title="Alfred V. Aho">Aho</a>, <a href="Jeffrey_Ullman" title="Jeffrey Ullman">Ullman</a> |
2021: <a href="Jack_Dongarra" title="Jack Dongarra">Dongarra</a> |
2022: <a href="Robert_Metcalfe" title="Robert Metcalfe">Metcalfe</a> |
2023: <a href="Avi_Wigderson" title="Avi Wigderson">Wigderson</a> |
2024: <a href="Andrew_Barto" title="Andrew Barto">Barto</a>, <a href="Richard_S._Sutton" title="Richard S. Sutton">Sutton</a>
</p>
</div></div>
<div class="hintergrundfarbe1 rahmenfarbe1 navigation-not-searchable normdaten-typ-p" style="border-style: solid; border-width: 1px; clear: left; margin-bottom:1em; margin-top:1em; padding: 0.25em; overflow: hidden; word-break: break-word; word-wrap: break-word;" id="normdaten">
<div style="display: table-cell; vertical-align: middle; width: 100%;">
<div>
Normdaten (Person): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/140808973">140808973</a></span> | <a href="Library_of_Congress_Control_Number" title="Library of Congress Control Number">LCCN</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/nr2003030022">nr2003030022</a></span> | <a href="Virtual_International_Authority_File" title="Virtual International Authority File">VIAF</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://viaf.org/viaf/38354675/">38354675</a></span> | </div>
</div></div>
</div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-08-07" href="https://de.wikipedia.org/wiki/?title=Stephen_A._Cook&oldid=258667899">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>